Software compilers use internal data structures (e.g., control flow graphs, data flow graphs, etc.) for maintaining abstract representations of a program being compiled. Among other things, these program representations are used for implementing optimization techniques (e.g., constant propagation, redundancy elimination, etc.). Thus, the form of internal data structure representations of a program can directly influence the power and effectiveness of the various optimization techniques.
More recently, static single assignment (SSA) form and control dependency graphs have been used for representing data flow and control flow of a program in an efficient manner so as to improve the effectiveness of the compiler optimization techniques. In particular, SSA form can be viewed as a sparse representation of the traditional use-definition and definition-use chains related to a program. The SSA form provides several advantages to optimizing compilers. For instance, in SSA form, strict discipline is imposed on the name space used for representing values in computation. Thus, each reference of a name in an SSA form corresponds to the value resulting from precisely a single assignment (this explains the “Single Assignment” in the name SSA). Also, in an SSA form, each use refers to a single name.
Thus, to produce SSA form, a compiler may rewrite the intermediate code representation by inventing new names for each definition and substituting these new names in subsequent uses of the original names. Typically, unique names are created by adding a subscript to the name provided in the original program code. For instance, if a program had a variable “X”, then an assignment to the variable in the program's SSA representation may be renamed “X1” whereas another assignment may be renamed as “X2” and so on. Such renaming is simple in the context of straight-line code. However, the presence of more complex control flow presents a challenge for such a renaming process and the interpretation of the resulting code. For instance, if a name in the original code is defined along two converging paths, the SSA form may have multiple names when it reaches a reference.
One way to solve this problem is to introduce a pseudo function (typically referred to as a phi-function, phi-function node, phi-node, φ-function, φ-function node or φ-node) which takes as its arguments the two renamed names converging at the paths and results in a single value being assigned to a new name depending on the control flow. The phi-function can be added into the SSA form where appropriate. For example, a phi-function such as φ(X1, X2) may resolve which value, X1 or X2, applies at a particular convergence path depending on how control flow reached that path (i.e., via the path 1 or 2). A phi-function is sometimes referred to as a “join” function.
Several methods have been proposed for constructing SSA form from the original code related to a program. Each method may result in varying forms of the SSA form with differences in the size of the name space and the number of phi-functions. For instance, Cytron et al. proposes a “minimal” construction for SSA form in their paper titled “Efficiently computing static single assignment form and the control dependence graph,” (ACM Transactions on Programming Languages and Systems, 13(4), 450-490, 1991). The so-called “minimal” construction inserts a phi-function at every point where a control-flow merge or join point brings together two SSA form names originating from a single name of the original code. However, this method may insert phi-functions that are unnecessary in an SSA form. For example, phi-functions may be inserted to resolve converging paths of a variable that are never used after the merge. Such values are also typically referred to as not being “live.”
The so-called “minimal” SSA construction as taught by Cytron et al. relies entirely on the dominance frontier information of the variables of the program, which accurately captures the potential flow of values in a program but ignores the actual facts related to the data-flow. In particular, Cytron et al. ignores any knowledge about the lifetimes of values determined from analyzing their definitions and uses. Because of this, the so-called “minimal” SSA construction method may in fact insert an unnecessary phi-function at a join point or a merge point for a variable that may not be live.
Several proposed methods address the unnecessary phi-functions. For instance, Choi et al. (Jong-Deok Choi, Ron Cytron, and Jeanne Ferrante; “Automatic Construction of Sparse Data Flow Evaluation Graphs,” Conference Record of the Eighteenth Annual ACM Symposium on Principles of Programming Languages, January 1991) propose a method for generating a pruned SSA form wherein all unnecessary phi-functions may be eliminated from the final SSA form. The method proposed by Choi et al. uses a traditional liveness analysis (e.g., via a backward walk) on the original, yet to be renamed variables in a prepass. In a different pass, Choi's method generates an SSA form relying on the liveness analysis, indicating which variables are live. However, such a process may be inefficient and time consuming because it requires multiple passes over the flow graph to generate a pruned SSA form without any unnecessary phi-functions.
A method of generating a so-called “Semi-Pruned” SSA form has also been proposed. For instance, Briggs et al., propose such a method in “Practical improvements to the construction and destruction of static single assignment form,” (Software: Practice and Experience, pages 28(8):859-881, 1998). This method proposes a less expensive local liveness analysis for each block of a control flow graph. However, this method does not always remove all the unnecessary phi-function nodes. Thus, there is a need for a method of generating a pruned SSA form which is efficient and accurate.